package bank;
import java.util.*;

public class _22GenerateBrackets {
    public static List<String> generateParenthesis(int n) {
        List<String> strs = new ArrayList<>();
        if(n == 1){
            strs.add("()");
            return strs;
        }
        //注意括号匹配问题有一个特征，当匹配成功时，从左向右读取括号数目时左括号数目一定不小于右括号数目！！！
        //递归算法
        Set<String> area = new HashSet<>();
        String iniStr = new String("()");
        insertStr(area,iniStr,n);
        for(String str : area){
            if(str.length() == n*2){
                strs.add(str);
            }
        }
        return strs;
    }

    /**
     * 注意：该算法用到递归，但是会添加括号数量少于目标数量的括号，也就是算法仍需改进
     * 这个算法的效率非常低，因为会添加无效元素，返回给generateParenthesis函数还需重新删掉无效元素
     */
    private static String insertStr(Set area, String iniStr, int n) {
        StringBuilder Str = new StringBuilder(iniStr);
        int i;
        if(--n == 0){
            //结束递归
            return Str.toString();
        }else {
            for(i = 0;i < Str.length();i++){
                Str.insert(i,"()");
                area.add(insertStr(area,Str.toString(),n));
                Str.delete(i,i+2);
            }
        }
        return Str.toString();
    }
}
